1. IntroductionQuantum walk, the quantum mechanical counterpart of classical random walk, has been recently shown to constitute a universal model of quantum computation.[1–3] Defined by analogy to classical random walk, a quantum walk is a time-homogeneous quantum process on a graph. Both random and quantum walks can be defined either in continuous or discrete time. Continuous- and discrete-time quantum walks are introduced as counterparts of classical continuous- and discrete-time random walks, respectively. However, unlike their classical counterparts, the discrete-time walk cannot simply reduce to the continuous-time walk as a limiting case. Two important types of discrete-time quantum walks are coined quantum walk (CQW) and scattering quantum walk (SQW). CQWs are defined on vertices with an auxiliary coin space representing the directions of walking. In SQWs, the particle resides on the edges of the graph. These two types of walks are unitary equivalent.[4]
The search problem is a major concern in cloud computing[5–7] and quantum properties have been exploited to solve classical problems.[8, 9] Quantum walks have been proven to be a useful framework in designing new quantum algorithms, the most notable of which are search algorithms.[10–17] Recent research have focused on the analysis of quantum search algorithms’ performance. It is generally difficult to quantify the dynamics of search algorithms. Ambainis brought about a generalization of Grover's algorithm, the abstract search algorithm,[11, 12] which characterizes the core of many existing search algorithms and ascertains their performance. Besides a general search for special vertices, recent studies have shown that quantum walks can also be used to find structural anomalies which affect a graph's symmetry.[18–20] A general formalism of a star graph S
N
with another graph G attached to one of its external vertices was established to analyze the search of structural anomalies.[21, 22] The overall graph is divided across the central vertex into two sides: G and the part which is connected to S
N
constitute the right side, and the remainder of the S
N
constitute the left side. Thus, the left side corresponds roughly to the initial state, which is intended to be rotated to the target state. It has been proven that these two sides must share the same eigenvalue when
to acquire a quadratic speedup, and quantum search helps to achieve this.
The topological structure plays an important role in quantum search algorithms on complete graphs, hypercubes and star graphs as well as in classical computer network.[23, 24] In the quantum-walk-based algorithms, graph automorphism that commutes with the evolutionary operator
is used to identify the invariant subspace of the entire space. With a carefully chosen initial state, quantum walk on the original graph effectively evolves on a “collapsed graph” that corresponds to the subspace. It was believed that the ideal problem to be solved by a quantum walk would be a problem with global symmetry. The phenomenon of reducing effective dimension due to the symmetry of the graph was analysed in detail in [25] for CQW and in [13] for SQW. Most recent research disapproved this conjecture by demonstrating that search on the known strongly regular graphs (SRGs), which are believed to have no global symmetry for large N, acquires quadratic speedup.[15]
We consider a search algorithm on SRGs in terms of discrete-time quantum walks. To quantify the performance of the search algorithm, we first divide the SRGs into two types and then leverage the techniques and results in [21] and [22] to provide a detailed analysis. We present the simulation results on two SRGs to provide an intuitive illustration. Our results confirm the conjecture in [22] that the theory on star graphs can be applied more generally.
2. PreliminariesThe Hilbert space of scattering quantum walk on graph
, with V being the set of vertices and E the set of edges, is defined as
, where jk is the edge connecting vertices j and k. Each edge corresponds to two states, i.e., one for each of the two possible directions. For each vertex
in G, there are two subspaces A
k
and
, which are spanned by the outgoing and incoming edges of k, respectively. Local unitary evolutions act as
, i.e., scattering on vertex k. The overall unitary operator
describing one step of SQW on graph G is the combined action of all the local unitary evolutions.
In a general search algorithm, there is a vertex which behaves differently from the others and the objective is to identify this target vertex. The local unitary operators act on vertex k as
, where r
k
and t
k
are reflection and transmission coefficients on vertex k, respectively. The target vertex reflects with a phase ϕ, which means that
,
. The phase shift operator acts as an oracle to mark the special vertex. An oracle is a black box that can recognize solutions to certain problems. In what follows ϕ is set to be π. For all the other vertices
,
, where d
k
is the degree of vertex k. This choice of local unitary operators is analogous to the choice of diffusive operator
in Grover's algorithm,[26] where
is the equal superposition of n states.
3. Search algorithm on SRGsIt is proved that “almost all” SRGs are asymmetric for large N. This means that their automorphism groups are trivial, and there is no automorphism taking a vertex to any other vertex. Thus, the method to collapse SRGs based on graph automorphism group, as given in [22], can no longer be applied. Nevertheless, we can construct an invariant subspace by the action of U on the graphs.
3.1. Collapsing SRGsFirst let us group the three types of vertices together: the target vertex t, its k adjacent vertices, denoted as a, and the remaining
vertices, denoted as b, which are not adjacent to the marked one. We then define the following edge states:
 | (1) |
 | (2) |
 | (3) |
 | (4) |
 | (5) |
 | (6) |
These six states form a subspace of the Hilbert space, which we will see is invariant under the action of the unitary operator. The collapsed graph of SRGs is defined as follows: the vertex set is
, and the edge set is composed of edge sates
to
, which correspond to directed edges
at,
ta,
aa,
ab,
ba,
bb, respectively, as shown in Fig.
2.
The initial state is chosen to be an equal superposition of all the edge states in the original SRGs, and can be expressed as
 | (7) |
Therefore, the initial state lies in the subspace.
As t is the target vertex,
. A simple way to obtain the action of
on the other states is by considering the effect of the Grover diffusion operator. Local unitary operator on vertex v (
mapping
is
, where
is the equal superposition of k edge states associated with v and
is the k-dimensional identity matrix. Each of the k adjacent vertices of vertex t has 1 edge connected to vertex t, λ connected to the other vertices in a, and the remaining
connected to the vertices in b. Thus, the 3D collapsed form of the k-dimensional
associated with the collapsed vertex a is
. The unitary operator on vertex a mapping
takes the form
Similarly, we can obtain the unitary operator on the collapsed vertex
b as
Thus, in the basis
, the unitary operator
on the subspace can be expressed as
 | (8) |
It is easy to verify that
. To quantify the performance, we divide the problem into two cases: when
k scales as
N and when
k scales less than
N, but not less than
from the definition of SRGs. We will see in the following subsections that the
case can be solved using Cottrell's formalism, while the
case cannot, and we resort to the matrix perturbation theory.
3.2. The
caseLet us give a brief review of techniques and results in [21] and [22]. Star graph S
N
with an unspecified graph G attached to one of the external vertices is divided into left and right segments, with the central vertex acting as a hub. For a general value of N denote operator
as
, the perturbation variable
in this case. When
, the leading-order matrix of
is
, a block diagonal matrix with two blocks
and
corresponding to the two sides. Considering the
-eigenspace of
, the left (right)
eigenvector refers to eigenvector native to
. The
eigenvector is called an active eigenvector if it will be affected when moving from the
case to the
case. There is a unique active eigenvector on each side of the hub vertex corresponding to eigenvalue
, denoted as
and
.
Fundamental pairing theorem
[22]
The
-eigenspace is in contact with both the left and right sides of the hub vertex if and only if there exist paired vectors
with eigenvalues of the form
, where
. With correctly chosen complex phases, the paired eigenvectors take the form
.
It was also shown that the optimal number of time steps for a search is
, and the probability of the state being either in G or on the edge between G and the hub is
.
The above formalism can be used to analyze structural anomalies in complete graphs.[20] Here is another application. The collapsed graph of SRGs in Fig. 2 is divided into two parts: the left part consists of vertex t, vertex a, and the collapsed edge between t and a; the right part consists of vertex a, the loops on a, vertex b, the loops on b, and the collapsed edge between a and b. Thus, the right part corresponds roughly to the initial state, which is intended to be rotated to the target states,
and
.
We consider Type-I SRGs. With
,
,
, the expression of
in Eq. (8) becomes
 | (9) |
Let
,
, the leading-and first-order terms of
in Eq. (
9) are, for large
μ,
The characteristic polynomial of
is
. It turns out that the only interesting eigenvalue is
, with right active eigenvector
and left active eigenvector
. Thus, the paired eigenvectors of
are
.
therefore, we have
. The initial state can be expressed as a superposition of two eigenvectors
. The optimal number of time steps for the search is
, and the probability of the state being on the edge connected to the target vertex is
.
Another double root of the characteristic polynomial of
is −1, with eigenvector
. However, in this case, the initial state has little overlap with the eigenspace spanned by the corresponding eigenvector, i.e.,
. In addition, the root is constant, which means it will not be affected by perturbation.
3.3. The
caseAs for
, we take the Latin square graph srg
for example. The unitary operator
reads
 | (10) |
For large
n, the leading-order terms of
in Eq. (
10) are
The characteristic polynomial of
is
. The double root −1 of
is a constant root and the associated eigenvector
has little overlap with the initial state. The only interesting eigenvalue is
and its corresponding eigenvectors are
and
for the right and left sides, respectively. Since
is not in contact with the hub vertex
a, we cannot use the fundamental pairing theorem to obtain the eigenspectrum of the evolutionary operator. It makes sense because if the theorem holds, we would acquire quadratic speedup over
.
The state of the walk after m steps is derived by employing the decomposition formula
, where
are the orthogonal eigenvectors corresponding to the eigenvalue λ of the unitary operator
. The typical approach to diagonalize
involves a perturbative approach to finding the eigenvalues and eigenstates, which is shown as follows. Although the pattern of calculation is basic, it involves tedious calculations. It can also be applied to the analysis of Type-I SRGs, which is included in the Appendix A.
For simplicity, we replace
with n, for large n. The characteristic polynomial of Eq. (10) is
which can be rewritten as
 | (11) |
Set
, and substitute it back into the fourth-order equation for
λ in Eq. (
11). Keeping only the lowest-order term, we obtain
, with roots
, where
. Let
, the eigenvalues can be expressed as
, with corresponding eigenvectors
. The initial state can also be expressed as a superposition of two eigenvectors
Applying
repeatedly for
m times yields
Starting from
, after
time steps, the particle is located on one of the edges connecting to target vertex with success probability
. The time complexity of these two examples is the same; however, the success probability of Latin square graphs is lower than that of Type-I SRGs
3.4. Simulation resultsTo intuitively illustrate the evolutionary process of the search algorithm, this subsection presents the numerical simulation results. Numerical simulation also allows us to compare the actual scaling with the bounds proved previously. First, consider the Paley graph with parameters (121, 60, 29, 30). We substitute the parameter set into Eqs. (7) and (8) to obtain the initial state and the evolutionary operator, respectively, of the search algorithm on SRG (121, 60, 29, 30) as
Figure
3 plots the results of simulating our algorithm for an increasing number of time steps.
To compare with the case in Section 3.3, we repeat the simulation process on an SRG with the same number of vertices as the Latin square graph with parameters (121, 20, 9, 2). Similarly, the initial state and the evolutionary operator can be obtained by substituting the parameter set (121, 20, 9, 2) into Eqs. (7) and (8), respectively. So we have
, and
Figure
4 shows the simulation results of the relationship between the number of iterations and the success probability.
As the evolutionary operator is unitary, the success probability changes quasi-periodically with the time evolution, which is confirmed by Figs. 3 and 4. In both the figures, the probability of the walkers being located on an edge connected to the target vertex are first amplified by the oracle operation until reaching the peak at t = 12 time steps, which is consistent with the analytical time complexity
. The maximum success probability is affected by the graph structure, with the former a little higher than the latter. This is consistent with the analytical results presented above, i.e.,
for the Paley Graphs and
for the Latin square graphs.
Appendix A
The characteristic polynomial of
in Eq. (9) is
i.e.,
 | (A1) |
When
, the zeroth-order polynomial is
. Set
, and substitute it back into the fourth-order equation for
λ in Eq. (
A1). Keeping only the lowest-order term, we find
, whose roots are
, where
. Thus the eigenvalues are
with associated eigenvectors
. The initial state is approximately equal to a superposition of two eigenvectors,
Applying
repeatedly for
m times yields
From the expression, we see that the probability amplitudes for edge states connected to target vertex are approximately equal to one when
. If we measure the position of the particle after
steps, it will, with probability
, be located on an edge connected to the target vertex.
